TreeSet and HashSet are two popular implementations of the Set interface in Java, each with distinct characteristics and use cases. 

HashSet

A HashSet is a collection of items where every item is unique and is found in the java.util package. Java HashSet class implements the Set interface, backed by a hash table which is actually a HashMap instance. No guarantee is made as to the iteration order of the hash sets which means that the class does not guarantee the constant order of elements over time. This class permits the null element. The class also offers constant time performance for the basic operations like add, remove, contains, and size assuming the hash function disperses the elements properly among the buckets, which we shall see further in the article.  

O(1) average time complexity for add, remove, and contains operations, assuming a good hash function and no hash collisions.

Java HashSet Features

A few important features of HashSet are mentioned below:

• Implements Set Interface.
• The underlying data structure for HashSet is Hashtable.
• As it implements the Set Interface, duplicate values are not allowed.
• Objects that you insert in HashSet are not guaranteed to be inserted in the same order. Objects are inserted based on their hash code.
• NULL elements are allowed in HashSet.
• HashSet also implements Serializable and Cloneable interfaces.

Syntax 

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable

Example -

// Java program to illustrate the concept of Collection objects storage in a HashSet
import java.io.*;
import java.util.*;

class CollectionObjectStorage {
  
    public static void main(String[] args)
    {
        // Instantiate an object of HashSet
        HashSet<ArrayList> set = new HashSet<>();

        // create ArrayList list1
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(45);

        // create ArrayList list2
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(49);
        
        // Add elements using add method
        list1.add(1);
        list1.add(2);
        list2.add(1);
        list2.add(2);
        set.add(list1);
        set.add(list2);

        // print the set size to understand the
        // internal storage of ArrayList in Set
        System.out.println(set);
    }
}

Output:

[[49, 1, 2], [45, 1, 2]]

 

TreeSet

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits the AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet class are stored in ascending order.

It is internally backed by a red-black tree (a self-balancing binary search tree). Maintains elements in a sorted (natural or custom) order. Elements are stored in a sorted order, either natural ordering or according to a provided Comparator. O(log n) time complexity for add, remove, and contains operations due to the tree structure.

Syntax

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable    

Example

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Orange");

        // Elements are in sorted order
        for (String element : treeSet) {
            System.out.println(element);
        }
    }
}

Summary of Differences

Feature	HashSet	TreeSet
Internal Structure	Hash table	Red-black tree
Ordering	No order	Sorted order
Performance	O(1) for basic operations	O(log n) for basic operations
Null Handling	Allows one null element	Does not allow null elements
Memory Overhead	Lower	Higher
Use Cases	Fast access, insertion, deletion	Sorted elements, range operations

• HashSet: Use when you need fast, unordered collection operations and can tolerate occasional hash collisions. Ideal for scenarios where insertion, deletion, and access times need to be minimal, and the order of elements does not matter.
• TreeSet: Use when you need a sorted set with guaranteed log(n) time complexity for basic operations. Ideal for scenarios requiring a sorted collection and efficient range of queries or when the natural ordering of elements is crucial.

 

Read more 

Compare ArrayList and LinkedList in Java. When would you use one over the other?

What is a HashMap in Java and how does it work internally?